package algorithm.poj.p2000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;


/**
 * 分析：
 * 这个问题还挺棘手的。
 * 一开始使用bitmap，发现即使这样空间和时间也不够，当N=10^7时，对应的数值接近10^9；
 * 
 * 如果仿1338, 2545那样用链表，时间远远不够。
 * 
 * 实现：
 * 经验：
 * 教训：
 * 分类：数学
 * 对比1338，2545
 * @author wong.tong@gmail.com
 *
 */
public class P2591 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P2591.class.getResource("P2591.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		int[] a = new int[10000000];
		a[0] = 1;
		int i2 = 0, i3 = 0;
		for (int i = 1; i < a.length; i ++) {
			a[i] = 2*a[i2]+1;
			int t = 3*a[i3]+1;
			if (t < a[i]) {
				a[i] = t;
				i3 ++;
			} else {
				if (t == a[i]) {
					i3 ++;
				}
				i2 ++;
			}
		}
		
		StringBuffer sb = new StringBuffer("");
		String line = stdin.readLine();
        while (line != null && !"0".equals(line.trim())) {
        	int n = Integer.valueOf(line);
        	sb.append(a[n-1]).append("\n");
	        line = stdin.readLine();
        }
        System.out.println(sb);
	}
	
}
